home *** CD-ROM | disk | FTP | other *** search
/ Sprite 1984 - 1993 / Sprite 1984 - 1993.iso / src / machserver / 1.098 / libc / memInt.h < prev    next >
C/C++ Source or Header  |  1991-04-27  |  13KB  |  348 lines
  1. /*
  2.  * memInt.h --
  3.  *
  4.  *    Defines things that are shared across the procedures that
  5.  *    do dynamic storage allocation (malloc, free, etc) but aren't
  6.  *    visible to users of the storage allocator.
  7.  *
  8.  * Copyright 1988 Regents of the University of California
  9.  * Permission to use, copy, modify, and distribute this
  10.  * software and its documentation for any purpose and without
  11.  * fee is hereby granted, provided that the above copyright
  12.  * notice appear in all copies.  The University of California
  13.  * makes no representations about the suitability of this
  14.  * software for any purpose.  It is provided "as is" without
  15.  * express or implied warranty.
  16.  *
  17.  * $Header: /sprite/src/lib/c/stdlib/RCS/memInt.h,v 1.6 90/10/11 22:12:06 kupfer Exp $ SPRITE (Berkeley)
  18.  */
  19.  
  20. #ifndef _MEMINT
  21. #define _MEMINT
  22.  
  23. #ifndef _SYNCUSER
  24. #include "sync.h"
  25. #endif
  26. #ifndef _STDLIB
  27. #include "stdlib.h"
  28. #endif
  29.  
  30. #include <cfuncproto.h>
  31.  
  32. /*
  33.  * If the MEM_TRACE flag is defined, extra code and data structures will
  34.  * be compiled to allow programs to trace malloc and free calls. 
  35. #define MEM_TRACE
  36. */
  37.  
  38. /*
  39.  * WARNING: several of the macros in this file expect both integers and
  40.  * pointers to be 32 bits (4 bytes) long.
  41.  */
  42.  
  43. /*
  44.  * This storage allocator consists of two independent allocators,
  45.  * one used for binned objects and the other used for large objects.
  46.  * Objects <= SMALL_SIZE are automatically binned, and all objects
  47.  * larger than BIN_SIZE are allocated with the large object
  48.  * allocator.  Objects in between these two sizes are normally
  49.  * allocated with the large allocator, but may be binned by calling
  50.  * Mem_Bin.
  51.  *
  52.  * Both allocators deal with "blocks" of storage, which correspond
  53.  * roughly to the areas that users request and free.  Each block of
  54.  * storage consists of an administrative area (usually a single word)
  55.  * followed by the useable area.  All allocations are done in even
  56.  * numbers of words, which means that clients may occasionally get more
  57.  * bytes than they asked for.  Malloc returns the address of the word
  58.  * just after the administrative area.  The first word of the administrative
  59.  * area is called the administrative word;  it allows us to keep track of
  60.  * which blocks are in use and which are free, and also to keep track of
  61.  * the sizes of blocks so clients don't have to know how large a block is
  62.  * when they free it.  The low-order bit of the administrative word
  63.  * indicates whether or not the block is free.  The next-to-low-order bit
  64.  * of the administrative word is used to indicate that this is a "dummy
  65.  * block":  for blocks on the un-binned list, this means that the block
  66.  * marks an area not belonging to the allocator;  for blocks returned to
  67.  * the "free" procedure, this means that the block must go back to the
  68.  * binned allocator.  The rest of the word tells how large the block is
  69.  * (in bytes including the administrative area).  Using the low-order bits
  70.  * for flags works because all blocks that we allocate are always multiples
  71.  * of 4 bytes in length.  There is one exception to this usage of the
  72.  * administrative word, which occurs for free binned objects.  In this
  73.  * case the word is a link to the next free binned object instead of a
  74.  * size.  If tracing is enabled, then the administrative area also contains
  75.  * a couple of other fields in addition to the administrative word.  The
  76.  * macros below define the format of the administrative area and how to
  77.  * access it.
  78.  */
  79.  
  80. #ifdef MEM_TRACE
  81.  
  82. typedef struct {
  83.     int        admin;        /* Administrative word. */
  84.     Address    pc;        /* PC of call to malloc. */
  85.     int        origSize;    /* Original size given to malloc. */
  86.     int        padding;    /* To make it double word aligned. */
  87. } AdminInfo;
  88.  
  89. #define GET_ADMIN(blockPtr)    (((AdminInfo *) (blockPtr))->admin)
  90. #define SET_ADMIN(blockPtr, value)  \
  91.             ((AdminInfo *) (blockPtr))->admin = (int) (value)
  92.  
  93. #define GET_PC(blockPtr)    (((AdminInfo *) (blockPtr))->pc)
  94. #define SET_PC(blockPtr)    ((AdminInfo *) (blockPtr))->pc = Mem_CallerPC()
  95.  
  96. #define GET_ORIG_SIZE(blockPtr)    (((AdminInfo *) (blockPtr))->origSize)
  97. #define SET_ORIG_SIZE(blockPtr,size)    \
  98.             ((AdminInfo *) (blockPtr))->origSize = size
  99.  
  100. #else
  101.  
  102. typedef double AdminInfo;
  103.  
  104. #define GET_ADMIN(blockPtr)    (*(int *)(AdminInfo *) (blockPtr))
  105. #define SET_ADMIN(blockPtr, value) *((int *)(AdminInfo *) (blockPtr)) = (int) (value)
  106.  
  107. #endif MEM_TRACE
  108.  
  109. #define USE_BIT        1
  110. #define DUMMY_BIT    2
  111. #define FLAG_BITS    3
  112. #define ADMIN_BITS(admin)    ((admin) & FLAG_BITS)
  113. #define IS_IN_USE(admin)    ((admin) & USE_BIT)
  114. #define IS_DUMMY(admin)        (((admin) & FLAG_BITS) == (USE_BIT|DUMMY_BIT))
  115. #define MARK_DUMMY(admin)    ((admin) | (USE_BIT|DUMMY_BIT))
  116. #define MARK_IN_USE(admin)    ((admin) | USE_BIT)
  117. #define MARK_FREE(admin)    ((admin) & ~FLAG_BITS)
  118. #define SIZE(admin)        ((admin) & ~FLAG_BITS)
  119.  
  120. /*
  121.  * The memory manager is a monitor.  The following definition is
  122.  * for its monitor lock.
  123.  */
  124.  
  125. extern Sync_Lock memMonitorLock;
  126. #define LOCKPTR (&memMonitorLock)
  127.  
  128.  
  129. /*
  130.  * ----------------------------------------------------------------------------
  131.  *
  132.  *    Binned-object allocator: it keeps a separate linked free list
  133.  *    for each size of object less than SMALL_SIZE bytes in size and
  134.  *    a free list for all objects less than BIN_SIZE that have been 
  135.  *    specified as being binned by a call to Mem_Bin.  The blocks on
  136.  *    each list are linked together via their administrative words
  137.  *    terminated by a NULL pointer.  Allocation and freeing are done in
  138.  *    a stack-like manner from the front of the free lists.
  139.  *
  140.  *    The following definitions are related:  if you change one, you'll
  141.  *    have to change several:
  142.  *
  143.  *    GRANULARITY: The difference in size between succesive buckets.  This
  144.  *        is determined by data alignment restrictions and should be
  145.  *        a power of 2 to allow for shifting to map from size to bucket.
  146.  *    SIZE_SHIFT: The shift distance to convert between size and bucket.
  147.  *    SMALL_SIZE:        largest blocksize (total including
  148.  *                administrative word) managed by default by
  149.  *                the binned-object allocator.
  150.  *    BIN_SIZE:        largest possible that can be binned.
  151.  *
  152.  *    These can be computed from the above constants.
  153.  *
  154.  *    SMALL_BUCKETS:        number of free lists corresponding to
  155.  *                sizes <= SMALL_SIZE.
  156.  *    BIN_BUCKETS:        total number of binned free lists.
  157.  *    BYTES_TO_BLOCKSIZE:    how many bytes a block must contain (total
  158.  *                including admin. word) to satisfy a user
  159.                 request in bytes.
  160.  *    BLOCKSIZE_TO_INDEX:    which free list to use for blocks of a given
  161.  *                size (total including administrative word).
  162.  *    INDEX_TO_BLOCKSIZE: the (maximum) size corresponding to a bucket.
  163.  *        This will include the size of the administrative word.
  164.  *
  165.  *    This is independent.
  166.  *
  167.  *    BLOCKS_AT_ONCE:        when allocating a new region to hold blocks of
  168.  *                a given size, how many blocks worth should
  169.  *                be allocated at once.
  170.  *
  171.  * ----------------------------------------------------------------------------
  172.  */
  173.  
  174. /*
  175.  * 8 byte granularity to handle SPUR and SPARC.
  176.  */
  177. #define GRANULARITY            8
  178. #define SIZE_SHIFT            3
  179. /*
  180.  * These sizes are optimized towards the kernels memory usage, 1/89.
  181.  */
  182. #define SMALL_SIZE            271
  183. #define    BIN_SIZE            4199
  184.  
  185. #define SMALL_BUCKETS            ((SMALL_SIZE+GRANULARITY-1)/GRANULARITY)
  186. #define BIN_BUCKETS            ((BIN_SIZE+GRANULARITY-1)/GRANULARITY)
  187. #define MASK                (GRANULARITY-1)
  188. #define BYTES_TO_BLOCKSIZE(bytes) ((bytes+MASK+sizeof(AdminInfo)) & (~MASK))
  189. #define BLOCKSIZE_TO_INDEX(size)  ((size)>>SIZE_SHIFT)
  190. #define INDEX_TO_BLOCKSIZE(index) ((index)<<SIZE_SHIFT)
  191.  
  192. #define BLOCKS_AT_ONCE            16
  193.  
  194. /*
  195.  * The following array holds pointers to the first free blocks of each size.
  196.  * Bucket i holds blocks whose total length is 4*i bytes (including the
  197.  * administrative info).  Blocks from bucket i are used to satisfy user
  198.  * requests ranging from (4*i)-sizeof(AdminInfo) bytes up to (4*i)-1 bytes.  
  199.  * Buckets 0 and 1 are never used, since they correspond to blocks too small
  200.  * to hold any information for the user.  If the list head is NOBIN, it
  201.  * means that this size isn't binned:  use the large block allocator.
  202.  */
  203.  
  204. extern Address    memFreeLists[BIN_BUCKETS];
  205. #define NOBIN    ((Address) -1)
  206.  
  207. /*
  208.  * Used to gather statistics about allocations:
  209.  */
  210.  
  211. extern int mem_NumBlocks[];        /* Total number of existing blocks,
  212.                      * both allocated and free, for each
  213.                      * small size.  */
  214. extern int mem_NumBinnedAllocs[];    /* Total number of allocation requests
  215.                      * made for blocks of each small size.
  216.                      */
  217.  
  218. /*
  219.  * ----------------------------------------------------------------------------
  220.  *    Large-object allocator:  used for blocks that aren't binned.
  221.  *    There should be relatively few allocations made by the
  222.  *    large-object allocator.  Since all the blocks it allocates are
  223.  *    relatively large, fragmentation should be less than it would be
  224.  *    if it allocated small blocks too. All of the blocks, in use or
  225.  *    not, are kept in a single linked list using their administrative
  226.  *    words.  The address of the next block in the list is found by
  227.  *    adding the size of the current block to the address of its
  228.  *    administrative word.  Things are complicated slightly because the
  229.  *    storage area managed by this allocator may be discontiguous:  there
  230.  *    could be several large regions that it manages, separated by gaps
  231.  *    that are managed by some other storage allocator (e.g. the
  232.  *    binned-object allocator).  In this case, the gaps between regions
  233.  *    are handled by making the gaps look like allocated blocks, with an
  234.  *    administrative word at the end of one region that causes a skip to
  235.  *    the beginning of the next region.  These blocks are called "dummy
  236.  *    blocks", and have special flag bits in their administrative words.
  237.  *    All the blocks within a region are linked together in increasing
  238.  *    order of address.  However, the different regions may appear in any
  239.  *    order on the list.
  240.  * ----------------------------------------------------------------------------
  241.  */
  242.  
  243. extern Address memFirst;        /* Pointer to first block of memory
  244.                      * in the un-binned pool. */
  245. extern Address memLast;            /* Points to dummy block at the end
  246.                      * of the memory list, which always
  247.                      * has zero size. */
  248. extern Address memCurrentPtr;        /* Next block to consider allocating.
  249.                      * Rotates circularly through free
  250.                      * list. */
  251. extern int memLargestFree;        /* This holds the size of the largest
  252.                      * free block that's been seen on the
  253.                      * free list.  It's updated as the
  254.                      * list is traversed.  */
  255. extern int memBytesFreed;        /* Sum of unbinned bytes freed since
  256.                      * the last time we started scanning
  257.                      * the memory list. */
  258.  
  259. /*
  260.  * Minimum size of new regions requested by large-object allocator
  261.  * when storage runs out:
  262.  */
  263.  
  264. #define MIN_REGION_SIZE 2048
  265.  
  266. /*
  267.  * Various stats about large-block allocator:  some are only kept when
  268.  * tracing is enabled.
  269.  */
  270.  
  271. extern int mem_NumLargeBytes;    /* Total amount of storage managed by
  272.                  * the large allocator.  */
  273. extern int mem_NumLargeAllocs;    /* Total number of allocation requests
  274.                  * handled by the large allocator.  */
  275. extern int mem_NumLargeLoops;    /* Number of iterations through the
  276.                  * inner block-checking loop of the
  277.                  * large allocator.  */
  278.  
  279. /*
  280.  * ----------------------------------------------------------------------------
  281.  *    Miscellaneous declarations.
  282.  * ----------------------------------------------------------------------------
  283.  */
  284.  
  285. /*
  286.  * Statistics about total calls to malloc and free.
  287.  */
  288.  
  289. extern int    mem_NumAllocs;
  290. extern int    mem_NumFrees;
  291.  
  292. /*
  293.  * Flag to make sure MemInit gets called once.
  294.  */
  295.  
  296. extern int    memInitialized;
  297.  
  298. /*
  299.  * If tracing is enabled, then when malloc or free is called a
  300.  * trace record will be printed and/or the number of blocks being used
  301.  * by the caller will be stored in the trace array if the block size is
  302.  * in sizeTraceArray. The array is defined with Mem_SetTraceSizes().
  303.  * PrintTrace calls a default printing routine; it can be changed with
  304.  * Mem_SetPrintProc().
  305.  */
  306. #define MAX_NUM_TRACE_SIZES    8
  307. #define    MAX_CALLERS_TO_TRACE    16
  308. typedef struct {
  309.     Mem_TraceInfo    traceInfo;
  310.     struct {
  311.     Address    callerPC;
  312.     int    numBlocks;
  313.     } allocInfo[MAX_CALLERS_TO_TRACE];
  314. } MemTraceElement;
  315.  
  316. extern MemTraceElement    memTraceArray[];
  317. extern    int        memNumSizesToTrace;
  318.  
  319. /*
  320.  * Routine to do printing for tracing and status printing.  Can be
  321.  * reset with Mem_SetPrintProc.
  322.  */
  323.  
  324. extern int        (*memPrintProc)(); /* e.g., fprintf */
  325. extern ClientData    memPrintData;
  326.  
  327. /*
  328.  * Can free storage be freed a second time?
  329.  */
  330.  
  331. extern int        memAllowFreeingFree;
  332.  
  333. /*
  334.  * Various procedures used internally by the allocator.
  335.  */
  336.  
  337. #ifdef KERNEL
  338. extern Address    MemChunkAlloc _ARGS_((int size, Address *addressPtr));
  339. #else
  340. extern Address    MemChunkAlloc _ARGS_((int size));
  341. #endif
  342.  
  343. extern void    MemDoTrace _ARGS_((Boolean allocated, Address infoPtr,
  344.                    Address curPC, int size));
  345. extern void    MemInit _ARGS_((void));
  346.  
  347. #endif _MEMINT
  348.